// 归并排序
/**
 * 将已有序的子序列合并，得到完全有序的序列，然后将两个有序表合并成一个
 * 
 * 算法描述：
 * - 递归法（Top-down）
    // 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
    // 设定两个指针，最初位置分别为两个已经排序序列的起始位置
    // 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
    // 重复步骤3直到某一指针到达序列尾
    // 将另一序列剩下的所有元素直接复制到合并序列尾
// - 迭代法（Bottom-up）
    // 原理如下（假设序列共有n个元素）：
    // 将序列每相邻两个数字进行归并操作，形成ceil(n/2)个序列，排序后每个序列包含两/一个元素
    // 若此时序列数不是1个则将上述序列再次归并，形成ceil(n/4)个序列，每个序列包含四/三个元素
    // 重复步骤2，直到所有元素排序完毕，即序列数为1
 * 

    复杂度：
        时间复杂度：O(nlogn)
        空间复杂度： O(n)
 * **/

function merge(leftArr, rightArr) {
    let res = [];
    while (leftArr.length > 0 && rightArr.length > 0) {
        if (leftArr[0] < rightArr[0]) {
            res.push(leftArr.shift());
        } else {
            res.push(rightArr.shift());
        };
    };

    return res.concat(leftArr).concat(rightArr);   // 合并
};


function mergeSort(arr) {
    if (arr.length === 1) return arr;
    let mid = Math.floor(arr.length / 2);  // 求中点
    let left = arr.slice(0, mid);
    let right = arr.slice(mid);
    return merge(mergeSort(left), mergeSort(right));
};


const arr = [32, 12, 56, 78, 76, 45, 36];

console.log(mergeSort(arr)); // [12, 32, 36, 45, 56, 76, 78]


